COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	%given to Pat Simmons
C00005 ENDMK
C⊗;
%given to Pat Simmons
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a68.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Equivalence in Languages\hfill}

Let $L$ be any language, whether or not recognized by a machine. We define
two equivalence relations associated with~$L$. 

\def\Lap{\buildrel L\over\approx}
\def\zap{\mathrel{\vbox{\lineskip1pt\baselineskip1pt
 \halign{\ctr{$##$}\cr
 \scriptscriptstyle L\cr \sim\cr}}}}

Two strings $x↓1$ and $x↓2$ are {\it prefix equivalent\/} in~$L$, 
$x↓1\Lap x↓2$, if for every string~$y$, both or neither of $x↓1y$ and
$x↓2y$ belong to~$L$. That is, 
$x↓1\zap x↓2$ iff $\forall y(x↓1y\in L\equiv x↓2y\in L)$.
To put it in another way, define $x\backslash L$, the {\it quotient\/}
of~$L$ by~$x$, as the set of strings~$y$ such that $xy\in L$; then
$x↓1\zap x↓2$ iff $x↓1\backslash L=x↓2\backslash L$. The latter definition
makessit clear that $\zap$ is aa equivalence relation.

Two strings $y↓1$ and $y↓2$ are {\it infix equivalent\/} in~$L$, 
$y↓1\Lap y↓2$, if for all strings $x$ and~$z$, both or neither of
$xy↓1z$ and $xy↓2z$ belong to~$L$. That is $y↓1\Lap y↓2$ iff
$\forall x,z(xy↓1z\in L\equiv xy↓2z\in L)$. 

\smallskip
{\bf Drill:} Show $\Lap$ is an equivalence relation.

\proclaim Theorem. $y↓1\Lap y↓2$ implies




\bigskip
\parindent0pt
\copyright 1988 Robert W. Floyd

First draft April 22, 1988.

\bye